import java.awt.*;
import java.awt.image.BufferedImage;
import java.util.*;
import java.util.List;
import java.util.logging.Logger;

//路径搜索，比如玩家从A点去B点
public class Map {
    //用于计算当前寻找路径的运算量
    int addNeighborCount;
    final int DIRECT_COST = 10;  // 横竖移动代价
    final int OBLIQUE_COST = 14;  // 斜移动代价

    Queue<Node> openList = new PriorityQueue<>(); // 优先队列(升序)
    List<Node> closeList = new ArrayList<>();
    int step = 5;

    public Node start; // 起始结点
    public Node end; // 最终结点
    
    Graphics bufferGraphics;  // 双缓冲图像的绘图上下文
    static public int width;
    static public int height;

    public static MapUnit[][] data; //搜索用
    public static MapUnit[][] data2; //备份用

    Color drawFoundPathColor = new Color(255,0,0);
    Color drawLineColor = new Color(0,0,255);
    Color drawFindingColor = new Color(0,255,0);
    BufferedImage bufferedImage;

    //打印日志工具，可以看到打印时当前类，方法，行，比便方便，sout不能看到这些信息不太方便
    Logger logger = MyLogger.getLogger();

    Map(BufferedImage bufferedImage, Image image)
    {
        width = bufferedImage.getWidth();
        height = bufferedImage.getHeight();
        data = new MapUnit[height][width];
        data2 = new MapUnit[height][width];
        this.bufferedImage = bufferedImage;
        this.bufferGraphics = image.getGraphics();
        for (int i = 0; i < height; i++)
        {
            for (int j = 0; j < width; j++)
            {
                int rgb = this.bufferedImage.getRGB(j, i);
                final int red = rgb & 0xff0000 >> 16;
                data[i][j] = (red > 230) ? MapUnit.IDLE : MapUnit.BAR; //不能走的区域 data[i][j] = 1;   //可以走的区域  data[i][j] = 0;
                data2[i][j] = data[i][j]; //不能走的区域 data[i][j] = 1;   //可以走的区域  data[i][j] = 0;
            }
        }
        //logger.info(Arrays.deepToString(data));
    }

    void resetBuffer()
    {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                int rgb = bufferedImage.getRGB(j, i);
                final int red = rgb & 0xff0000 >> 16;
                //logger.info(String.valueOf(red));
                if (red > 230)  //可以走的区域
                {
                    data[i][j] = MapUnit.IDLE;
                    bufferGraphics.setColor(new Color(255, 255, 255));
                }
                else //不能走的区域
                {
                    data[i][j] = MapUnit.BAR;
                    bufferGraphics.setColor(new Color(0, 0, 0));
                }
                bufferGraphics.drawLine(j, i, j, i);
            }
        }

        //graphics.drawImage(bufferedImage, 0, 0, width, height, null);
    }

    /**
     * 判断结点是否是最终结点
     */
    private boolean isEndNode(Coord end,Coord coord)
    {
        return end.equals(coord);
    }

    /**
     * 判断结点能否放入Open列表
     */
    private boolean canAddNodeToOpen(Coord coord)
    {
        // 超出地图像素大小
        if (coord.x < 0 || coord.x >= width || coord.y < 0 || coord.y >= height)
            return false;

        // 判断是否是不可通过的结点
        if (data[coord.y][coord.x] == MapUnit.BAR) return false;

        // 判断结点是否存在close表
        return !isInCloseList(coord);
    }

    void dataRecovery()
    {
        start = null;
        end = null;

        //因为搜索路径会修改地图数组，搜索完成后要恢复数组的内容
        for (int i = 0; i < height; i++)
        {
            //如果不是小兵或者玩家才恢复
            if (width >= 0) System.arraycopy(data2[i], 0, data[i], 0, width);
        }
    }

    /**
     * 判断坐标是否在close表中
     */
    private boolean isInCloseList(Coord end)
    {
        if (end == null)
            return false;

        if (closeList.isEmpty())
            return false;

        for (Node node : closeList)
        {
            if (node.coord.x == end.x && node.coord.y == end.y)
            {
                return true;
            }
        }
        return false;
    }

    private int calcH(Coord end,Coord coord)
    {
        return Math.abs(end.x - coord.x) + Math.abs(end.y - coord.y);
    }

    private Node findNodeInOpen(Coord coord)
    {
        //logger.info("");
        if (coord == null || openList.isEmpty()) return null;

        for (Node node : openList)
        {
            if (node.coord.equals(coord))
            {
                return node;
            }
        }
        return null;
    }

    /**
     * 添加所有邻结点到open表
     */
    private void addNeighborNodeInOpen(Node current)
    {
        int x = current.coord.x;
        int y = current.coord.y;

        bufferGraphics.setColor(drawFindingColor);
        bufferGraphics.fillRect(x, y, 3, 3); //这步比较消耗资源，注释掉会快很多
        addNeighborCount++;

        // 左
        addNeighborNodeInOpen(current, x - step, y, DIRECT_COST);

        // 上
        addNeighborNodeInOpen(current, x, y - step, DIRECT_COST);

        // 右
        addNeighborNodeInOpen(current, x + step, y, DIRECT_COST);

        // 下
        addNeighborNodeInOpen(current, x, y + step, DIRECT_COST);

        // 左上
        addNeighborNodeInOpen(current, x - step, y - step, OBLIQUE_COST);

        // 右上
        addNeighborNodeInOpen(current, x + step, y - step, OBLIQUE_COST);

        // 右下
        addNeighborNodeInOpen(current, x + step, y + step, OBLIQUE_COST);

        // 左下
        addNeighborNodeInOpen(current, x - step, y + step, OBLIQUE_COST);
    }

    /**
     * 添加一个邻结点到open表
     */
    private void addNeighborNodeInOpen(Node current, int x, int y, int value)
    {
        if (canAddNodeToOpen(new Coord(x, y)))
        {
            Node end1=end;
            Coord coord = new Coord(x, y);
            int G = current.G + value; // 计算邻结点的G值
            Node child = findNodeInOpen(coord);
            if (child == null)
            {
                int H=calcH(end1.coord,coord); // 计算H值
                if(isEndNode(end1.coord,coord))
                {
                    child=end1;
                    child.parent=current;
                    child.G=G;
                    child.H=H;
                }
                else
                {
                    child = new Node(coord, current, G, H);
                }
                openList.add(child);
            }
            else if (child.G > G)
            {
                child.G = G;
                child.parent = current;

                // 重新调整堆
                openList.add(child);
            }
        }
    }

    private void drawFoundPath(Node end, ArrayList<Coord> coordArrayList)
    {
        if(end == null || data == null)
            return;

        while (end != null)
        {
            Coord c = end.coord;
            data[c.y][c.x] = MapUnit.FOUND_PATH;
            bufferGraphics.setColor(drawFoundPathColor);
            bufferGraphics.fillRect(c.x, c.y, 3, 3);
            coordArrayList.add(c);
            end = end.parent;
        }
    }

    public ArrayList<Coord> pathFindInit(Coord start1, Coord end1)
    {
        if (start1.x >= width || start1.y >= height ||end1.x >= width || end1.y >= height )
        {
            logger.info("start or end outof index, can not find path...");
            return null;
        }

        if (data[start1.y][start1.x] != MapUnit.IDLE || data[end1.y][end1.x] != MapUnit.IDLE)
        {
            logger.info("start or end must bar, can not find path...");
            dataRecovery();
            return null;
        }

        //这里除step再乘以step为了加速搜索，建议使用5这种比较容易搜索到的路坐标++++
        start = new Node(start1.x / step * step, start1.y / step * step);
        end = new Node(end1.x / step * step, end1.y / step * step);

        // clean
        openList.clear();
        closeList.clear();
        ArrayList<Coord> coordArrayList = new ArrayList<>();
        pathFindStart(coordArrayList);
        return coordArrayList;
    }

    /**
     * 移动当前结点
     */
    private void pathFindStart(ArrayList<Coord> coordArrayList)
    {
        //添加第一个结点
        openList.add(start);

        // 开始搜索
        while (!openList.isEmpty())
        {
            Node current = openList.poll();
            closeList.add(current);

            //关键步骤
            if (current != null) {
                addNeighborNodeInOpen(current);
            }

            if (isInCloseList(end.coord)) // 如果终点坐标在closeList里已经有，表示找到路径
            {
                drawFoundPath(end, coordArrayList);
                logger.info(" addNeighborCount " + addNeighborCount);

                addNeighborCount = 0;
                dataRecovery();

                break;
            }
        }
    }
}